package _interview100;

import java.util.HashMap;
import java.util.Map;

/**
 * 76. 最小覆盖子串
 */
public class No76 {
    Map<Character, Integer> origin = new HashMap<>();
    Map<Character, Integer> current = new HashMap<>();

    public String minWindow(String s, String t) {
        int m = s.length();
        for (char c : t.toCharArray()) {
            origin.put(c, origin.getOrDefault(c, 0) + 1);
        }

        String ans = "";
        int len = Integer.MAX_VALUE;

        int left = 0, right = 0;
        while (right < m) {
            if (origin.containsKey(s.charAt(right))) {
                current.put(s.charAt(right), current.getOrDefault(s.charAt(right), 0) + 1);
            }
            while (left <= right && check()) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    ans = s.substring(left, right + 1);
                }
                if (origin.containsKey(s.charAt(left))) {
                    current.put(s.charAt(left), current.getOrDefault(s.charAt(left), 0) - 1);
                }
                left++;
            }
            right++;
        }
        return ans;
    }

    public boolean check() {
        for (Map.Entry<Character, Integer> entry : origin.entrySet()) {
            if (current.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}
